package com.zjj.algorithm.learning.leetcode.linkedlist;

/**
 * 1669. 合并两个链表 中档题
 * 给你两个链表 list1 和 list2 ，它们包含的元素分别为 n 个和 m 个。
 * <p>
 * 请你将 list1 中下标从 a 到 b 的全部节点都删除，并将list2 接在被删除节点的位置。
 * <p>
 * 下图中蓝色边和节点展示了操作后的结果：
 * 输入：list1 = [0,1,2,3,4,5], a = 3, b = 4, list2 = [1000000,1000001,1000002]
 * 输出：[0,1,2,1000000,1000001,1000002,5]
 * 解释：我们删除 list1 中下标为 3 和 4 的两个节点，并将 list2 接在该位置。上图中蓝色的边和节点为答案链表。
 * <p>
 * <p>
 * 输入：list1 = [0,1,2,3,4,5,6], a = 2, b = 5, list2 = [1000000,1000001,1000002,1000003,1000004]
 * 输出：[0,1,1000000,1000001,1000002,1000003,1000004,6]
 * 解释：上图中蓝色的边和节点为答案链表。
 *
 * @author zjj_admin
 * @date 2022/11/17 13:47
 */
public class MergeInBetweenLinkedLists {


    /**
     * 输入：list1 = [0,1,2,3,4,5,6], a = 2, b = 5, list2 = [1000000,1000001,1000002,1000003,1000004]
     * 输出：[0,1,1000000,1000001,1000002,1000003,1000004,6]
     * 时间
     * 1 ms
     * 击败
     * 100%
     * 内存
     * 44.5 MB
     * 击败
     * 84.54%
     *
     * @param list1
     * @param a
     * @param b
     * @param list2
     * @return
     */
    public static ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {

        // list1 = [0,1,2,3,4,5,6], a = 2, b = 5,
        // list2 = [1000000,1000001,1000002,1000003,1000004]
        //让node节点指向 list1，node指向 list1 的0
        ListNode node = list1;
        //让node指向最后一个不会被删除的节点,
        for (int i = 0; i < a - 1; i++) {
            node = node.next;
        }
        //此时node指向 list1 的1
        //让node1节点指向第一个要被删除的节点，node1 指向 list1 的 2
        ListNode node1 = node.next;
        //让node1 向后遍历，直到超过最后一个要被删除的节点，遇到后面的那个不会被删除的节点
        for (int i = 0; i < b - a + 1; i++) {
            node1 = node1.next;
        }
        //此时node1 指向 list1 的6
        //让node【list1中的1】指向list2中的 1000000
        node.next = list2;
        while (node.next != null) {
            node = node.next;
        }
        //此时node指向了list2中的 1000004
        // 让node1 的next 指向 list1 中的 6
        node.next = node1;
        return list1;
    }

}
